#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <sstream>

/* tokyocabinet library */
#include <tcutil.h>
#include <tchdb.h>
#include <tcbdb.h>
#include <tcfdb.h>
#include <tcadb.h>

namespace pocketj_plus {

  enum {
    MAXDEPTH = 1,
  };

  typedef std::map<int, std::vector<std::map<int, int > > > Index;

  const std::string MAX_WORD_ID = "MAX_WORD_ID";

  namespace util {

    std::vector<std::string> split(std::string str, std::string delim)
    {
      std::vector<std::string> result;
      uint64_t cutAt;
      while((cutAt = str.find_first_of(delim)) != str.npos){
        if(cutAt > 0) result.push_back(str.substr(0, cutAt));
        str = str.substr(cutAt + 1);
      }
      if(str.length() > 0) result.push_back(str);
      return result;
    }

    void ucsToUtf(uint16_t c, int num, std::string& result) {
      uint16_t buf[num];
      buf[0] = c;
      const uint16_t* ary = buf;
      char rv[4];
      tcstrucstoutf(ary, 1, rv);
      result = rv;
    }

    void getNgram(std::vector<std::string>& ngram, std::string doc, unsigned int num)
    {
      std::vector<std::string> queue;
      std::vector<std::string>::iterator itr;
      int anum;
      uint16_t stack[66563];
      uint16_t* ary = stack;
      tcstrutftoucs(doc.c_str(), ary, &anum);
      for (int i = 0; i < anum ; i++) {
        uint16_t cBuf = ary[i];
        std::string c;
        pocketj_plus::util::ucsToUtf(cBuf, 1, c);
        if (queue.size() < num) {
          queue.push_back(c);
        } else {
          std::string token;
          for (unsigned int i = 0; i < queue.size(); i++) {
            token += queue.at(i);
          }
          itr = queue.begin();
          queue.erase(itr);
          queue.push_back(c);
          ngram.push_back(token);
        }
      }
      std::string token;
      for (unsigned int i = 0; i < queue.size(); i++) {
        token += queue.at(i);
      }
      ngram.push_back(token);
    }

    int createRandomInt(int max) {
      int rv = static_cast<int>(std::rand() % max);
      return rv;
    }

    std::string createRandomString() {
      std::string rv;
      int wd;
      int num = createRandomInt(100);
      for(int i = 0; i < num; i++){
        wd         = std::rand() % 26 + 97;
        char wdbuf = static_cast<char>(wd);
        rv         = rv + wdbuf;
      }
      return rv;
    }
  }

  class Feature {
    friend class LessAn;
  public:
    Feature(){}

    Feature(int id, int df)
    {
      this->id = id;
      this->df = df;
    }

    ~Feature(){}

    void setID(int id)
    {
      this->id = id;
    }

    void setDF(int df)
    {
      this->df = df;
    }

    int getID()
    {
      return id;
    }

    int getDF()
    {
      return df;
    }

  private:
    int id;
    int df;
  };

  class Doc {

  public:
    Doc()
    {
      featureNum = 0;
    }

    ~Doc() {}

    void setFeatureNum(int featureNum)
    {
      this->featureNum = featureNum;
    }

    void setFeature(const std::vector<Feature>& features)
    {
      this->features = features;
    }

    int getFeatureNum()
    {
      return featureNum;
    }

    void itrInit()
    {
      itr = features.begin();
    }

    bool getNextFeature(int& id, int& df)
    {
      if (itr == features.end()) return false;
      Feature feature = *itr;
      id = feature.getID();
      df = feature.getDF();
      itr++;

      return true;
    }

    bool getFeature(int index, int& id, int& df)
    {
      if (index > featureNum) return false;
      Feature feature = features[index];
      id = feature.getID();
      df = feature.getDF();
      return true;
    }

  private:
    int featureNum;
    std::vector<Feature> features;
    std::vector<Feature>::iterator itr;
  };

  class LessAn {
  public:
    bool operator() (const Feature& a, const Feature&b) {
      return a.df < b.df;
    }
  };


  class Analyzer {
    friend class POCKETJTestCase;
  public:
    Analyzer(double threshold, double param, std::string path) :
      T(threshold),
      PARAM(param), // ookikunaru hodo zatu ni naru.
      DOC_ID_KEY(1),
      WORD_ID_KEY(2),
      DOC_LENGTH_KEY(3)
    {
      openDB(path);
    }

    ~Analyzer()
    {
      closeDB();
    }

    bool addDoc(int docID, std::string& str)
    {
      if (docSave.find(docID) != docSave.end()) return false;
      std::vector<std::string> ngram;
      pocketj_plus::util::getNgram(ngram, str, 2);
      std::vector<Feature> featureList;
      std::map<std::string, int> tokenID;
      std::map<std::string, int>::iterator itr;
      Doc doc;
      unsigned int featureSiz = ngram.size();
      for (unsigned int i = 0; i < featureSiz; i++) {
        int id = 1;
        std::string token = ngram.at(i);
        if ((itr = tokenID.find(token)) != tokenID.end()) {
          id += itr->second;
        }
        tokenID.insert(std::pair<std::string, int>(token, id));
        char* idStr     = tcsprintf("%d", id);
        std::string key = token + "_" + idStr;
        free(idStr);
        char* keyID = tchdbget2(wordIdHdb, key.c_str());
        if (!keyID) {
          char* maxIDBuf = tchdbget2(wordIdHdb, pocketj_plus::MAX_WORD_ID.c_str());
          int maxID      = std::atoi(maxIDBuf) + 1;
          free(maxIDBuf);
          keyID = tcsprintf("%d", maxID);
          tchdbput2(wordIdHdb, pocketj_plus::MAX_WORD_ID.c_str(), keyID);
          tchdbput2(wordIdHdb, key.c_str(), keyID);
        }
        tchdbaddint(dfHdb, keyID, std::strlen(keyID), 1);
        Feature feature(std::atoi(keyID), 1);
        featureList.push_back(feature);
        free(keyID);
      }
      doc.setFeatureNum(featureSiz);
      doc.setFeature(featureList);
      docSave.insert(std::make_pair<int, Doc>(docID, doc));
      std::vector<int> docIDSiz(2);
      docIDSiz[1] = docID;
      docIDSiz[0] = featureSiz;
      queue.push(docIDSiz);

      return true;
    }

    void sortDoc()
    {
      std::map<int, Doc>::iterator itr = docSave.begin();
      std::map<int, Doc> docSaveBuf;
      while (itr != docSave.end()) {
        int docID = itr->first;
        Doc doc   = itr->second;
        std::vector<Feature> features;
        doc.itrInit();
        int id, df;
        //int newFeatureNum = 0;//
        while ((doc.getNextFeature(id, df)) != false) {
          char* idBuf = tcsprintf("%d", id);
          char* dfBuf = tchdbget2(dfHdb, idBuf);
          int df      = dfBuf ? *(int*)dfBuf : 0;
          free(dfBuf);
          free(idBuf);
          //          if (df > 1) {//
            Feature feature(id, df);
            features.push_back(feature);
            //newFeatureNum++;//
        }
        sort(features.begin(), features.end(), LessAn());
        doc.setFeature(features);
        //doc.setFeatureNum(newFeatureNum); //

        itr++;
        docSave.erase(docID);
        docSave.insert(std::make_pair<int, Doc>(docID, doc));
      }
    }

    bool doJoin(std::map<int, std::set<int> >& result)
    {
      int xID;
      while((getIDFromQueue(xID)) != false) {
        std::map<int, int> A;
        Doc xDoc    = docSave[xID];
        int xLength = xDoc.getFeatureNum();
        double p    = std::ceil(xLength - (T * xLength) + 1);
        int wID, df;
        int wi = 1;
        xDoc.itrInit();
        while((xDoc.getNextFeature(wID, df)) != false) {
          Index::iterator idxItr = index.find(wID);
          if (idxItr != index.end()) {
            std::vector<std::map<int, int> > yIndex = idxItr->second;
            for (unsigned int i = 0; i < yIndex.size(); i++) {
              std::map<int, int> yMapBuf = yIndex[i];
              int yID     = yMapBuf[DOC_ID_KEY];
              int yLength = yMapBuf[DOC_LENGTH_KEY];
              int yj      = yMapBuf[WORD_ID_KEY];
              Doc yDoc    = docSave[yID];
              if (xID == yID) {
                continue;
              }
              if (yLength >= T * xLength) {
                double tt     = (T / (1 + T));
                int lengthh   = xLength + yLength;
                double alpha  = ( tt * lengthh);
                double ubound = getUbound(xLength, wi, yLength, yj);
                int Ay        = A[yID];
                if (Ay + ubound >= alpha) {
                  double hMax = getHmax(xLength, wi, yLength, yj);
                  std::vector<Feature> xDocVec;
                  int id = 0;
                  int df = 0;
                  for (int i = wi; i < xLength; i++) {
                    xDoc.getFeature(i, id, df);
                    Feature ft(id, df);
                    xDocVec.push_back(ft);
                  }
                  std::vector<Feature> yDocVec;
                  for (int i = yj; i < yLength; i++) {
                    yDoc.getFeature(i, id, df);
                    Feature ft(id, df);
                    yDocVec.push_back(ft);
                  }

                  int H = suffixFilter(xDocVec, yDocVec, hMax, 1);

                  if (H <= hMax) {
                    A[yID] = Ay + 1;
                  }
                } else {
                  //A[yID] = 0;
                }
              }
            }
          }
          addWordToIndex(wID, xID, wi, xLength);
          wi++;
          if (wi > p) break;
        }

        //verify
        std::vector<int> relatedDocs;
        verify(A, xDoc, p, xID, relatedDocs);

        if (relatedDocs.size() > 0) {
          std::set<int> relatedIDs;
          for (unsigned int i = 0; i < relatedDocs.size(); i++) {
            relatedIDs.insert(relatedDocs[i]);
          }
          std::set<int>::iterator itr = relatedIDs.begin();
          while (itr != relatedIDs.end()) {
            int rID = *itr;
            if ((result.find(rID)) != result.end()) {
              std::set<int> relatedIDsBuf = result[rID];
              std::set<int>::iterator i;
              for(i = relatedIDsBuf.begin(); i != relatedIDsBuf.end(); i++) {
                relatedIDs.insert(*i);
              }
              result.erase(rID);
            }
            result.insert(std::make_pair<int, std::set<int> >(xID, relatedIDs));
            itr++;
          }
        }
      }
      return true;
    }

  private:
    const double T;
    const int PARAM;
    const int DOC_ID_KEY;
    const int WORD_ID_KEY;
    const int DOC_LENGTH_KEY;
    TCHDB* dfHdb;
    TCHDB* wordIdHdb;
    std::priority_queue<std::vector<int> > queue;
    Index index;
    std::map<int, Doc> docSave;
    enum {
      TRUNC = HDBOWRITER|HDBOCREAT|HDBOTRUNC,
      READ  = HDBOREADER,
    };

    bool getIDFromQueue(int& docID)
    {
      int queueSiz = queue.size();
      if (queueSiz <= 0) return false;
      std::vector<int> buf = queue.top();
      docID = buf.at(1);
      queue.pop();
      return true;
    }

    double getUbound(int xLength, int xWordID, int yLength, int yWordID)
    {
      double ubound = 0;
      int xMin      = xLength - xWordID;
      int yMin      = yLength - yWordID;
      int min       = (xMin >= yMin) ? yMin : xMin;
      return ubound = PARAM + min;
    }

    void addWordToIndex(int word, int docID, int wordID, int length)
    {
      std::map<int, int> mapBuf;
      mapBuf.insert(std::make_pair<int, int>(DOC_ID_KEY, docID));
      mapBuf.insert(std::make_pair<int, int>(WORD_ID_KEY, wordID));
      mapBuf.insert(std::make_pair<int, int>(DOC_LENGTH_KEY, length));
      index[word].push_back(mapBuf);
    }

    void verify(std::map<int, int>& A,
                Doc& x, int p, int xID, std::vector<int>&  result)
    {
      std::map<int, int>::iterator itrA = A.begin();
      while(itrA != A.end()) {
        int yID  = itrA->first;
        int yVal = itrA->second;
        if (yVal > 0) {
          int px        = p;
          int xLength   = x.getFeatureNum();
          Doc y         = docSave[yID];
          int yLength   = y.getFeatureNum();
          int py        = std::ceil(yLength - (T * yLength) + 1);
          int O         = yVal;
          double alpha  = (T / (1 + T)) * (xLength + yLength);
          double ubound = 0;
          if (px < py) {
            ubound = yVal + xLength - px;
            if (ubound > alpha) {
              std::map<int, int> xFeatures;
              int wID, df;
              for (int i = px + 1; i < xLength; i++) {
                x.getFeature(i, wID, df);
                xFeatures.insert(std::make_pair<int, int>(wID, 1));
              }
              for (int i = yVal + 1; i < yLength; i++) {
                y.getFeature(i, wID, df);
                if ((xFeatures.find(wID)) != xFeatures.end()) {
                  O++;
                }
              }
            }
        } else {
            ubound = yVal + yLength - py;
            if (ubound > alpha) {
              std::map<int, int> xFeatures;
              int wID, df;
              for (int i = yVal + 1; i < xLength; i++) {
                x.getFeature(i, wID, df);
                xFeatures.insert(std::make_pair<int, int>(wID, 1));
              }
              for (int i = py + 1; i < yLength; i++) {
                y.getFeature(i, wID, df);
                if ((xFeatures.find(wID)) != xFeatures.end()) O++;
              }
            }
          }
          if (O >= alpha) {
            result.push_back(yID);
          }
        }
        itrA++;
      }
    }

    bool openDB(std::string& path)
    {
      bool rv = true;
      std::string dfPath = path + "df.hdb";
      dfHdb = tchdbnew();
      if(!tchdbopen(dfHdb, dfPath.c_str(), pocketj_plus::Analyzer::TRUNC)) {
        rv = false;
      }

      std::string wordIdPath = path + "word_id.hdb";
      wordIdHdb = tchdbnew();
      if(!tchdbopen(wordIdHdb, wordIdPath.c_str(), pocketj_plus::Analyzer::TRUNC)) {
        rv = false;
      }
      tchdbput2(wordIdHdb, pocketj_plus::MAX_WORD_ID.c_str(), "0");

      return rv;
    }

    bool closeDB()
    {
      tchdbclose(wordIdHdb);
      tchdbdel(wordIdHdb);
      tchdbclose(dfHdb);
      tchdbdel(dfHdb);
      return true;
    }

    double getHmax(int xLength, int xNo, int yLength, int yNo)
    {
      double hMax = xLength + yLength +
              (-2 * (T / (1 + T)) * (xLength + yLength)) - ( xNo + yNo - 2);

      return hMax;
    }

    int suffixFilter(std::vector<Feature>& x, std::vector<Feature>& y,
                     double hMax, int d)
    {
      int xLength = x.size();
      int yLength = y.size();
      int xyDiff  = std::abs(xLength - yLength);
      if (d > pocketj_plus::MAXDEPTH){
        return xyDiff;
      }
      if (x.size() == 0 || y.size() == 0) {
        return hMax + 1;
      }

      int mid = static_cast<int>(std::ceil(static_cast<double>(yLength) / 2)) - 1;
      Feature wBuf     = y.at(mid);
      double numerator = (float)hMax - xyDiff;
      double o = (numerator == 0) ? 0 : numerator / 2;
      int oL, oR;
      if (xLength < yLength) {
        oL = 1;
        oR = 0;
      } else {
        oL = 0;
        oR = 1;
      }
      int f;
      int diff;
      std::vector<Feature> yL;
      std::vector<Feature> yR;
      partition(y, wBuf, mid, mid, yL, yR, f, diff);
      std::vector<Feature> xL;
      std::vector<Feature> xR;
      int lBound = (mid + 1) - o - std::abs(xLength - yLength) * oL;
      int rBound = (mid + 1) + o + std::abs(xLength - yLength) * oR;
      partition(x, wBuf, lBound, rBound, xL, xR, f, diff);

      if (f == 0) {
        return hMax + 1;
      }

      int xLSiz = xL.size();
      int xRSiz = xR.size();
      int yLSiz = yL.size();
      int yRSiz = yR.size();

      int H = std::abs(xLSiz - yLSiz) + std::abs(xRSiz - yRSiz) + diff;

      if (H > hMax) {
        //std::cout << "here" << std::endl;
        return H;
      } else {
        int llBound = hMax - std::abs(xRSiz - yRSiz) - diff;
        int Hl = suffixFilter(xL, yL, llBound, d + 1);
        H = Hl + std::abs(xRSiz - yRSiz)+ diff;
        if (H <= hMax) {
          int rrBound = hMax - Hl - diff;
          int Hr = suffixFilter(xR, yR, rrBound, d + 1);
          return Hl + Hr + diff;
        }  else {
          return H;
        }
      }
    }

    void partition(std::vector<Feature>& s, Feature& wBuf, int l, int r,
                   std::vector<Feature>& sL, std::vector<Feature>& sR,
                   int& f, int& diff)
    {
      if (l < 0 || r > static_cast<int>(s.size()) - 1) {
        f    = 0;
        diff = 1;
        return;
      }

      if (l > r) {
        f    = 0;
        diff = 1;
        return;
      }
      int w = wBuf.getID();
      int wDf = wBuf.getDF();

      Feature sl = s.at(l);
      int slDf   = sl.getDF();

      Feature sr = s.at(r);
      int srDf   = sr.getDF();

      if (slDf > wDf || srDf < wDf) {
        f = 0;
        diff = 1;
        return;
      }
      f = 1;
      int p = binarySearch(s, wDf, l, r);

      for (int i = 0; i < p - 1; i++) {
        sL.push_back(s[i]);
      }
      if (s[p].getID() == w) {
        for (unsigned int i = p + 1; i < s.size(); i++) {
          //if (s[i].getID() == w) {
          //continue;
          //}
          sR.push_back(s[i]);
        }
        diff = 0;
      } else {
        for (unsigned int i = p; i < s.size(); i++) {
          sR.push_back(s[i]);
        }
        diff = 1;
      }
    }

    int binarySearch(std::vector<Feature>& s, int wDf, int l, int r)
    {
      if (l > static_cast<int>(s.size()) || r > static_cast<int>(s.size())) {
        return 0;
      }
      int low   = l;
      int high  = r;

      /*
      for (unsigned int i = 0; i < s.size(); i++) {
        Feature ft = s.at(i);
        std::cout << ft.getID() << ":" << ft.getDF()  << " | ";
      }
      std::cout << std::endl;
      */

      int p = -1;
      int middle;
      while (low <= high) {
        middle = (low + high) / 2;
        Feature middleWord = s[middle];
        int middleWordDf = middleWord.getDF();

        if (wDf == middleWordDf) {
          p = middle; // found
          break;
        }

        if (wDf < middleWordDf) {
          high = middle - 1;
        } else {
          low = middle + 1;
        }
        p = middle;
      }

      int j = 0;
      for (j = p; j > 0; j--) {
        Feature word = s.at(j);
        int wordDf = word.getDF();
        if (wordDf < wDf) {
          j++;
          break;
        }
      }

      return j;
    }

    int stringToInt(std::string& num)
    {
      std::stringstream stream;
      stream << num.data();
      int buf;
      stream >> buf;
      return buf;
    }
  };
}
